DP G
from 動的計画法
DP_G
G
グラフの最長パスを見つける問題
DP_G bad
1TLE
code:python
def solve(N, M, edges):
longest = -1 * (N + 1)
def get_longest(start):
if longeststart != -1:
return longeststart
next_edges = edges.get(start)
if not next_edges:
ret = 0
else:
ret = max(get_longest(v) for v in edgesstart) + 1
longeststart = ret
return ret
return max(get_longest(v) for v in edges)
Python 428 ms AC
code:python
def solve(N, M, edges):
longest = -1 * (N + 1)
for i in range(N + 1):
if not edgesi:
longesti = 0
def get_longest(start):
next = edgesstart
for v in next:
if longestv == -1:
longestv = get_longest(v)
ret = max(longestv for v in next) + 1
return ret
for i in range(N + 1):
if longesti == -1:
longesti = get_longest(i)
return max(longestv for v in edges)
Cython
https://atcoder.jp/contests/dp/submissions/14906046